Computer networks often use packet-switching for transmitting messages, such as web pages and e-mail, along a path between a source and a destination on the network. An example of the basic topology of a packet-switched network is illustrated in FIG. 1, and the Internet is one example of a packet-switched network.
In a packet-switched network 10, messages to be transmitted are first divided into smaller discrete packets, which when transmitted may take different paths from a source 12 to a destination 14. When all of the packets arrive at the destination they are recompiled into the original message. The arrangement of the communication links or “hops” between the various devices of the packet-switched network is a partially connected mesh topology where many of the devices are not directly connected to the other devices. Therefore, transmitting messages over a packet-switched network requires a device at the intersection of the links to guide packets from one link to another link along the packet's path.
Guiding packets along the path from the source 12 to the destination 14 includes routing and switching functions. Routing involves the examination of the packet to determine, among other things, the address of the next device in the network to send the packet to, i.e., determining the outgoing link for the packet. Switching involves actually directing packets to the outgoing link that corresponds to the next device in the network, i.e., switching the packet from the incoming link to the outgoing link.
In a packet-switched network, a router 16 performs both routing and switching. Having multiple ports coupled with different links in the network, the router receives packets from an incoming link, examines a header of the packet to determine the outgoing link for the packet, and then transmits the packet on the outgoing link. The packet includes a portion of the message to be transmitted, and a header that includes destination information for the packet. In particular, routers make routing decisions based on an Internet Protocol (IP) destination address contained within the header. Generally, in a “lookup” operation, the router compares the IP destination address to a number of potential paths stored in a forwarding table, and then assigns the outgoing link to the packet. The header may also contain quality of service (QoS) data, which designates the priority with which the packet should be serviced by the router.
The IP destination address (or Layer 3 destination address) is a 32-bit identifier assigned to a device on a TCP/IP packet-switched network. The 32-bit IP address is subdivided into four numbers between 0 and 255 separated by periods, e.g., 10.230.15.255. The subdivisions of the IP address are hierarchical, representing from left to right greater specificity as to the destination for the packet. For example, the left most “10” portion of the exemplary address may represent the East Coast, the “230” portion may represent New York City, the “15” portion may represent a local area network (“LAN”) in the Empire State Building, and “255” may represent the intended final destination in the LAN for the packet. To properly route a packet, a router 16 need only have an output port associated with a portion of the IP destination address, such as one of the subdivision. For example, the router might transmit all packets having an IP destination address beginning with “10” on the outgoing link attached with a second router on the East Coast, which will then determine where to send the packet to next. Accordingly, a packet may make several hops along its path from the source 12 to the destination 14.
The IP addressing scheme of a packet-switched network 10 provides for scalability of the network, in that each router 16 need not be directly connected with the destination 14 for the packet. To manage scalability, the addition or removal of devices from the network is tracked and updated by the routing or forwarding table, which is typically dynamic. Routing protocol software provides communication between routers on the network and updates the forwarding table in each router to reflect changes in the topology of the network.
Conventional routers can suffer from a “denial of service attack” wherein the route processor of a conventional router is interrupted each time a route processor destined packet is received by the router. If a hacker generates a large number of route processor destined packets to a particular router, then that router may experience performance problems, and possibly shut down, if the route processor is continually interrupted so that it can deal with the receipt and processing of the route processor destined the packets.
Packets come in many different sizes ranging from 20 bytes to thousands of bytes, and are generally transmitted into a router at a line rate of, for example, 40 gigabytes per second (Gbps). It may be problematic for conventional routers to perform the required routing table lookup operations for a series of smaller sized packets flowing into the conventional router at the 40 Gbps line rate without having to drop packets. If a packet is dropped, then the packet must be retransmitted, which slows the overall message transmission time. To avoid dropping packets, conventional routers frequently are “input-striped” in that as they receive packets from the network, the packets are divided into a number of fixed length units referred to as “cells,” and the cells are written to a large buffer memory before performing the forwarding table lookup operations and determining the outgoing link for the packet. Such an input-striping process makes the initial front end writing process into the buffer memory rather simple, however, it is often difficult to read out the cells and reassemble the cells into a packet because packets are processed out of order in general within the router, which adds latency to the transmission of the packet.
In conventional routers, the input buffer memory required to store the incoming packets while the lookup is performed must be large to avoid overflowing the input buffer memory. Moreover, an additional large switching memory is generally required to store the packets for a period of time after the lookup operations are performed, but before the packet is transmitted to the correct outgoing link of the router. Accordingly, in order to avoid duplication of large high-speed memories, prior art devices oftentimes use a single memory for both the input buffering and the switching memory.
Oftentimes input-striping involves storing the cells non-contiguously in whatever portions of the single memory are available. The cells then stay in the single memory while the lookup is performed and the QoS priority for the packet is determined. As a consequence, the storage of the cells in the single memory is not a function of the outgoing link for the packet or the QoS priority for the packet because the outgoing link and the priority are unknown at the time the packet is cellified and stored. As an additional consequence, when the conventional router is ready to transmit the packet, the cells of the packet must be located in the single memory and then extracted. This generally requires a significant memory management scheme including, for example, memory pointers, link lists, and link list arrays to find and extract the cells from the single memory.
As recognized by the present inventors, what is needed is a packet routing and switching device, such as a router, which provides lookup processing of any size packet at the incoming link line rate while reducing the risk that packets are dropped. It is against this background that various embodiments of the present invention were developed.